#include "stock.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <list>
#include <cstdlib>
#include <unordered_map>
using namespace std;
//SimpleCuttingPlanner类实现
//输入同CuttingPlanner，调用solve()获取结果int指针，调用getlen()获取结果长度
struct Plan2
{
    int remainder;
    int repeat;
    vector<int> ids;
    Plan2(int size)
    {
        remainder = 0;
        repeat = 0;
        ids.assign(size, 0);
    }
};
class SimpleCuttingPlanner {
public:
    SimpleCuttingPlanner(int types, int* lengths, int* counts, int rawLength, int maxCombination) : _rawLength(rawLength), _maxCombination(maxCombination)
    {
        int cursor = 0;
        for (size_t i = 0; i < types; i++)
        {
            bool unique = true;
            for (size_t j = 0; j < _lengths.size(); j++)
            {
                if (*(lengths + i) == _lengths[j])
                {
                    unique = false;
                    _counts[j] += *(counts + i);
                }
            }
            if (unique)
            {
                _lengths.push_back(*(lengths + i));
                _counts.push_back(*(counts + i));
                cursor++;
            }
        }
        _types = cursor;
    };

    int* solve() 
    {
        list<int> part;
        for (size_t i = 0; i < _types; i++)
        {
            part.insert(part.end(), _counts[i], _lengths[i]);
        }
        part.sort(greater<int>());
        vector<Rawsolution> res;
        Rawsolution raw(_rawLength, _maxCombination); //初始化一根空的
        res.push_back(raw);
        while (!part.empty())
        {
            int item = part.front();
            part.pop_front();
            bool placed = false;
            size_t i = 0;
            for (; i < res.size(); i++)
            {
                placed = res[i].ifRoom(item);
                if (placed)
                    break;
            }
            if (!placed)
            {
                res.push_back(raw);
                res[i].ifRoom(item);
            }
        }
        vector<Plan2> solution;
        Plan2 plan(_types);
        solution.push_back(plan);
        solution[0].ids = _lengths;
        unordered_map<int, int> mymap;
        for (size_t i = 0; i < _types; i++)
        {
            mymap.insert(pair<int, int>(_lengths[i], i));
        }
        int k = 1;
        for (size_t i = 0; i < res.size(); i++)
        {
            Plan2 p(_types);
            p.remainder = _rawLength;
            for (size_t j = 0; j < res[i].sol.size(); j++)
            {
                p.remainder -= res[i].sol[j];
                int id = mymap[res[i].sol[j]];
                p.ids[id] += 1;
                p.repeat += 1;
            }
            if (p.ids != solution.back().ids)
            {
                solution.push_back(p);
            }
            else solution.back().repeat++;
        }
        _retLen = (solution.size()) * (_types + 2);
        int* ret;
        ret = (int*)malloc((_retLen) * sizeof(int));
        for (size_t i = 0; i < solution.size(); i++)
        {
            for (size_t j = 0; j < _types + 2; j++)
            {
                int k = (i) * (_types + 2) + j;
                if (j < _types)
                    *(ret + k) = solution[i].ids[j];
                else if (j == _types)
                    *(ret + k) = solution[i].remainder;
                else
                    *(ret + k) = solution[i].repeat;
            }
        }
        return ret;
    }
    int getLen()
    {
        return _retLen;
    }
private:
    int _types;
    int _rawLength;
    int _maxCombination;
    int _retLen = 0;
    vector<int> _lengths;
    vector<int> _counts;
    vector<Plan2> bestPlan;
};

//int main()
//{
//#if 0
//    int a[] = { 100, 150, 350, 450, 130, 480, 500, 160, 460, 20, 10, 250, 72, 168, 345, 189, 423, 360, 440, 110, 263, 369, 100, 52, 78, 10, 20, 60, 236, 410, 50, 60, 71, 74, 263, 46, 352, 120 };
//    int size = sizeof(a) / sizeof(a[0]);
//#else
//    int len[20] = { 1600, 1560, 1400, 1380, 1300, 1260, 1100, 1000, 960, 860, 800, 760, 700, 680, 600, 500, 460, 400, 380, 300 }; //20个输入
//    int cou[20] = { 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 };
//    int* l = len;
//    int* c = cou;
//#endif
//    SimpleCuttingPlanner plan(20, l, c, 6000, 4);
//    int* s = plan.solve();
//    int length = plan.getLen();
//    for (int i = 0; i < length; i++)
//    {
//        if ((i) % 22 == 0)
//            cout << endl;
//        cout << *(s + i) << " ";
//    }
//    return 0;
//}